#include <iostream>
using namespace std;

typedef int elemType;

typedef struct Node
{
    elemType data;
    Node *next;
} Node,*nodep;

typedef struct List
{
    int length;
    Node *head;
} List, *listp;

void initList(listp L)
{
    L->head = NULL;
    L->length = 0;
}

void prepend(listp L, elemType e)
{
    Node *newNode = new Node();
    newNode->data = e;
    newNode->next = L->head;
    L->head = newNode;
    L->length++;
}

void append(listp L, elemType e)
{
    if (L->length == 0)
    {
        return prepend(L, e);
    }
    else
    {
        Node *h = L->head;
        while (h != NULL && h->next != NULL)
        {
            h = h->next;
        }
        Node *newNode = new Node();
        newNode->data = e;
        newNode->next = NULL;
        h->next = newNode;
        L->length++;
    }
}
void showList(listp L)
{
    cout << "the length of list is " << L->length << endl;
    Node *h = L->head;
    while (h != NULL )
    {
        cout<<">> "<<h->data<<endl;
        h = h->next;
    }
}
void insert(listp L,int index,elemType e){
    if (index > L->length && index<0)  {
        cout<<"error: index out of range ! : "<<index<<endl;
        return;
    }
    if(index == 0) return prepend(L,e);
    if(L->length == index) return append(L,e);
    Node* h = L->head;
    int count=0;
    while(h->next!=NULL && count<index-1){
        h = h->next;
        count++;
    }
    cout<<h->data<<endl;
    Node *newNode = new Node();
    newNode->data = e;
    newNode->next = h->next;
    h->next = newNode;
    L->length++;
}

nodep locateElem(listp L,elemType e){
    Node* h = L->head;
    while (h->next!=NULL){
        if (h->data == e){
            return h;
        }
        h = h->next;
    }
    return NULL;
}

elemType findMax(listp L){
    int max = -10000000;
    Node *h = L->head;
    while (h != NULL )
    {
        max = h->data>max?h->data:max;
        h = h->next;
    }

    return max;
}


listp reverseList(listp L){
    if (L->length == 0)
    {
        cout<<"error: no elements on list "<<endl;
    }
    nodep first = L->head;
    nodep second = L->head->next;
    nodep third = NULL;
    while(second){
        third = second->next;
        second->next = first;
        first = second;
        second = third;
    }
    L->head->next = NULL;
    L->head = first;
    return L;
}

listp getIntercept(listp a,listp b){
    nodep ha = a->head;
    nodep hb = b->head;
    initList(a);
    cout<<a->head;
    while (ha!=NULL&&hb!=NULL)
    {
        if(ha->data<hb->data){
            ha=ha->next;
        }
        if (ha->data>hb->data){
            hb =hb->next;
        }
        if(ha->data == hb->data){
            append(a,ha->data);
            ha = ha->next;
            hb = hb->next;
        }
        
    }
    return a;
}

listp getDiff(listp a,listp b){
    nodep ha = a->head;
    nodep hb = b->head;
    initList(a);
    cout<<a->head;
    while (ha!=NULL&&hb!=NULL)
    {
        if(ha->data==hb->data){
            ha=ha->next;
            hb = hb->next;
        }else{
            append(a,ha->data);
            ha = ha->next;
        }
        
    }
    while(ha!=NULL){
        append(a,ha->data);
        ha = ha->next;
    }
    return a;
}

void test1(){
    List *list = new List();
    List *list2 = new List();
    initList(list);
    initList(list2);
    append(list,1);
    append(list,2);
    append(list2,2);
    append(list,3);
    append(list,4);
    append(list2,4);
    append(list,5);
    showList(list);
    // getIntercept(list,list2);
    // showList(getIntercept(list,list2));
    showList(getDiff(list,list2));
}

void test2(){
    List *list = new List();
    List *list2 = new List();
    initList(list);
    initList(list2);
    append(list,1);
    append(list,2);
    append(list2,2);
    append(list,3);
    append(list,4);
    append(list2,4);
    append(list,5);
    showList(list);
    // getIntercept(list,list2);
    showList(getIntercept(list,list2));
    // showList(getDiff(list,list2));
}



int main()
{   
    test1();
    test2();
}